Thus, it is natural to endow each state with a distribution over the tokens it may emit.

We are grateful to the reviewers for their feedback. We address all their comments below. We will fix the typo on line 142. Reviewer #2: Thank you very much for your feedback. We provide additional results to address all your concerns.

The authors propose three online inference methods, i.e., peek search, randomized peek search, and peek reset, for Markov chain models. They also use a proof framework to prove the competitive ratio for each method. The proof method first computes the lower bound of ON, so that gets the relationship between the ON and OPT. And then it uses the properties of geometric series to find an upper bound of competitive ratio. The authors also design a dynamic programming method to efficiently compute reward accumulation, and prove its complexity.

We resolve the fundamental problem of online decoding with ergodic Markov models. Specifically, we provide deterministic and randomized algorithms that are provably near-optimal under latency constraints with respect to the unconstrained offline optimal algorithm. Our algorithms admit efficient implementation via dynamic programs, and extend to (possibly adversarial) non-stationary or time-varying Markov settings as well. Moreover, we establish lower bounds in both deterministic and randomized settings subject to latency requirements, and prove that no online algorithm can perform significantly better than our algorithms.